Introduction

• Quadratic reciprocity is one of the most famous results in number theory.
• It describes a deep symmetry between the solvability of $$x^2 \equiv p \pmod q \quad\text{and}\quad x^2 \equiv q \pmod p$$ for odd primes $p$ and $q$.
• At first glance, these two questions seem unrelated.
• The law reveals a hidden pattern that mathematicians found astonishing for centuries.

A Curious Asymmetry… or Is It?

• Suppose $p$ and $q$ are two odd primes.
• You might ask:
  • Is $p$ a quadratic residue modulo $q$?
  • Is $q$ a quadratic residue modulo $p$?
• These look like two separate questions.
• Early mathematicians computed tables and noticed:
  • Sometimes the answers match.
  • Sometimes they don’t.
  • But the mismatches follow a very specific rule.
• This rule is the Law of Quadratic Reciprocity.

Quadratic Residues Across Different Primes

• For each odd prime $p$, the Legendre symbol is $$\left(\frac{a}{p}\right)$$
• It tells us whether $a$ is a quadratic residue mod $p$. $$\left( \frac{a}{p} \right) = \begin{cases} \;\;1 & \text{if $a$ is a quadratic residue mod $p$ and } a\not\equiv 0 \\ -1 & \text{if $a$ is a non‑residue mod $p$} \\ \;\;0 & \text{if } p \mid a \end{cases}$$
• We are interested in the special case:
  • $\left(\frac{p}{q}\right)$
  • $\left(\frac{q}{p}\right)$
• These symbols encode the solvability of:
  • $x^2 \equiv p \pmod q$
  • $x^2 \equiv q \pmod p$
• The surprising fact: these two symbols are almost the same.

Patterns That Seem to Almost Line Up

When you compute small examples, you notice:

• For many pairs of primes $(p,q)$: $$\left(\frac{p}{q}\right) = \left(\frac{q}{p}\right).$$
• But for some pairs: $$\left(\frac{p}{q}\right) = -\left(\frac{q}{p}\right).$$

A pattern emerges:

• The “sign flip” happens exactly when both primes are $\equiv 3 \pmod 4$.
• This is the heart of quadratic reciprocity.

Exploring the Symmetry Through Examples

Example 1: $p=3$, $q=11$

• $3 \equiv 3 \pmod 4$, $11 \equiv 3 \pmod 4$ → both $3 \pmod 4$
• Expect a sign flip.
• Compute:
  • Squares mod $11$: $1,4,9,5,3$ → $3$ is a residue → $\left(\frac{3}{11}\right)=1$
  • Squares mod $3$: $1$ → $11 \equiv 2$ mod $3$ is not a residue → $\left(\frac{11}{3}\right)=-1$
• Indeed: $1 = -(-1)$.

Example 2: $p=5$, $q=13$

• $5 \equiv 1 \pmod 4$ → no sign flip.
• Compute:
  • Squares mod $13$: $1,4,9,3,12,10$ → $5$ is not a residue → $\left(\frac{5}{13}\right)=-1$
  • Squares mod $5$: $1,4$ → $13 \equiv 3$ mod $5$ is not a residue → $\left(\frac{13}{5}\right)=-1$
• They match.

The Reciprocity Phenomenon (Informal First Look)

A rough, intuitive version:

• If $p$ and $q$ are odd primes:
  • Usually, $p$ is a square mod $q$ if and only if $q$ is a square mod $p$.
  • The only time this symmetry breaks is when both primes are of the form $4k+3$.
• In that special case, the answers are opposite.

This is already a remarkable statement.

The Law of Quadratic Reciprocity (Formal Statement)

For distinct odd primes $p$ and $q$: $$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{(p-1)(q-1)}{4}}.$$ This exponent is $1$ exactly when both $p$ and $q$ are $\equiv 3 \pmod 4$.

So the law can be stated more simply:

• If at least one of $p$ or $q$ is $\equiv 1 \pmod 4$, then $$\left(\frac{p}{q}\right) = \left(\frac{q}{p}\right).$$
• If both are $\equiv 3 \pmod 4$, then $$\left(\frac{p}{q}\right) = -\left(\frac{q}{p}\right).$$

The Two Supplementary Laws

Quadratic reciprocity is accompanied by two simpler rules:

1. The First Supplementary Law (for $-1$)

For an odd prime $p$: $$\left(\frac{-1}{p}\right) = \begin{cases} 1 & \text{if } p \equiv 1 \pmod 4,\\ -1 & \text{if } p \equiv 3 \pmod 4. \end{cases}$$

2. The Second Supplementary Law (for $2$)

For an odd prime $p$: $$\left(\frac{2}{p}\right) = \begin{cases} 1 & \text{if } p \equiv \pm 1 \pmod 8,\\ -1 & \text{if } p \equiv \pm 3 \pmod 8. \end{cases}$$ These help compute Legendre symbols quickly.

Why This Law Is So Surprising

• The solvability of $x^2 \equiv p \pmod q$ seems unrelated to $x^2 \equiv q \pmod p$.
• Yet the law shows a precise relationship.
• Historically:
  • Gauss called it the “gem of arithmetic”.
  • It was the first major theorem to reveal a deep symmetry in number theory.
• It connects:
  • Modular arithmetic
  • Symmetry
  • Prime numbers
  • Hidden structure in the integers

A High‑Level Proof Roadmap

There are many proofs (Gauss found eight).

• Gauss’s Lemma approach
  • Count how many multiples of $p$ fall into certain intervals modulo $q$.
  • Compare with the reverse situation.
  • A parity argument gives the reciprocity law.
• Lattice point / geometric approach
  • Count points in a rectangle.
  • Compare two ways of counting.
  • A symmetry argument emerges.
• Finite field approach
  • Use properties of multiplicative characters.
  • Show that a certain product behaves symmetrically.

Applications and Consequences

Quadratic reciprocity helps with:

• Quickly determining whether $x^2 \equiv a \pmod p$ has a solution.
• Simplifying computations in cryptography (e.g., primality testing).
• Understanding deeper reciprocity laws in algebraic number theory.
• Building intuition for more advanced topics like:
  • Dirichlet characters
  • Class field theory
  • Higher reciprocity laws

Summary and Key Ideas

• Quadratic reciprocity links two seemingly unrelated questions.
• The Legendre symbols $\left(\frac{p}{q}\right)$ and $\left(\frac{q}{p}\right)$ are usually equal.
• They differ only when both primes are $\equiv 3 \pmod 4$.
• Supplementary laws help compute special cases.
• The theorem is a cornerstone of number theory and a gateway to deeper ideas.

Calculator

Exercises

1. Compute $\left(\frac{3}{7}\right)$ and $\left(\frac{7}{3}\right)$ and verify quadratic reciprocity.

   Solution

   Compute $\left(\frac{3}{7}\right)$ and $\left(\frac{7}{3}\right)$ and verify quadratic reciprocity.

   • Step 1: $\left(\frac{3}{7}\right)$

     Squares mod $7$:

     • $1^2 \equiv 1$
     • $2^2 \equiv 4$
     • $3^2 \equiv 2$
     • $4^2 \equiv 2$
     • $5^2 \equiv 4$
     • $6^2 \equiv 1$

     Quadratic residues mod $7$ are $1,2,4$.
     Since $3$ is not in this list, $$\left(\frac{3}{7}\right) = -1.$$

   • Step 2: $\left(\frac{7}{3}\right)$

     Reduce $7$ mod $3$: $7 \equiv 1 \pmod 3$.
     So $$\left(\frac{7}{3}\right) = \left(\frac{1}{3}\right) = 1,$$ because $1$ is always a square.

   • Check reciprocity

     $3 \equiv 3 \pmod 4$, $7 \equiv 3 \pmod 4$ → both $3 \pmod 4$, so we expect a sign flip: $$\left(\frac{3}{7}\right) = -\left(\frac{7}{3}\right).$$ Indeed, $-1 = -1\cdot 1$.

2. Compute $\left(\frac{5}{11}\right)$ and $\left(\frac{11}{5}\right)$.

   Solution

   Compute $\left(\frac{5}{11}\right)$ and $\left(\frac{11}{5}\right)$.

   • Step 1: $\left(\frac{5}{11}\right)$

     Squares mod $11$:

     • $1^2 \equiv 1$
     • $2^2 \equiv 4$
     • $3^2 \equiv 9$
     • $4^2 \equiv 5$
     • $5^2 \equiv 3$
     • $6^2 \equiv 3$ (then it repeats)

     Quadratic residues mod $11$ are $1,3,4,5,9$.
     Since $5$ is in the list, $$\left(\frac{5}{11}\right) = 1.$$

   • Step 2: $\left(\frac{11}{5}\right)$

     Reduce $11$ mod $5$: $11 \equiv 1 \pmod 5$.
     So $$\left(\frac{11}{5}\right) = \left(\frac{1}{5}\right) = 1.$$

   • Check reciprocity

     $5 \equiv 1 \pmod 4$, $11 \equiv 3 \pmod 4$ → at least one is $1 \pmod 4$, so no sign flip: $$\left(\frac{5}{11}\right) = \left(\frac{11}{5}\right) = 1.$$

3. Use the supplementary laws to compute $\left(\frac{-1}{19}\right)$ and $\left(\frac{2}{19}\right)$.

   Solution

   Use the supplementary laws to compute $\left(\frac{-1}{19}\right)$ and $\left(\frac{2}{19}\right)$.

   • First supplementary law (for $-1$)

     $19 \equiv 3 \pmod 4$, so $$\left(\frac{-1}{19}\right) = -1.$$

   • Second supplementary law (for $2$)

     Compute $19 \pmod 8$: $19 \equiv 3 \pmod 8$.
     For $p \equiv \pm 3 \pmod 8$, we have $\left(\frac{2}{p}\right) = -1$.
     So $$\left(\frac{2}{19}\right) = -1.$$

4. Use quadratic reciprocity to compute $\left(\frac{13}{17}\right)$ without listing squares.

   Solution

   Use quadratic reciprocity to compute $\left(\frac{13}{17}\right)$ without listing squares.

   • Step 1: Use reciprocity

     Both $13$ and $17$ are odd primes.
     Check mod $4$:

     • $13 \equiv 1 \pmod 4$
     • $17 \equiv 1 \pmod 4$

     So no sign flip: $$\left(\frac{13}{17}\right) = \left(\frac{17}{13}\right).$$

   • Step 2: Reduce the top

     $17 \equiv 4 \pmod{13}$, so $$\left(\frac{17}{13}\right) = \left(\frac{4}{13}\right).$$

   • Step 3: Simplify $\left(\frac{4}{13}\right)$

     $4 = 2^2$, so $4$ is clearly a square modulo any odd prime.
     Thus $$\left(\frac{4}{13}\right) = 1.$$

   • Conclusion $$\left(\frac{13}{17}\right) = 1.$$
5. Determine whether $x^2 \equiv 29 \pmod{43}$ has a solution.

   Solution

   Determine whether $x^2 \equiv 29 \pmod{43}$ has a solution.

   We need $\left(\frac{29}{43}\right)$.

   • Step 1: Use reciprocity

     Check mod $4$:

     • $29 \equiv 1 \pmod 4$
     • $43 \equiv 3 \pmod 4$

     At least one is $1 \pmod 4$, so no sign flip: $$\left(\frac{29}{43}\right) = \left(\frac{43}{29}\right).$$

   • Step 2: Reduce

     $43 \equiv 14 \pmod{29}$, so $$\left(\frac{43}{29}\right) = \left(\frac{14}{29}\right).$$

   • Step 3: Factor $14$

     $14 = 2 \cdot 7$, so $$\left(\frac{14}{29}\right) = \left(\frac{2}{29}\right)\left(\frac{7}{29}\right).$$

   • Step 4: Compute $\left(\frac{2}{29}\right)$

     $29 \equiv 5 \pmod 8$ (since $29 = 3\cdot 8 + 5$).
     For $p \equiv \pm 3 \pmod 8$, $\left(\frac{2}{p}\right) = -1$;
     for $p \equiv \pm 1 \pmod 8$, $\left(\frac{2}{p}\right) = 1$.
     Here $5 \equiv -3 \pmod 8$, so $29 \equiv -3 \pmod 8$, hence $$\left(\frac{2}{29}\right) = -1.$$

   • Step 5: Compute $\left(\frac{7}{29}\right)$ via reciprocity

     Check mod $4$:

     • $7 \equiv 3 \pmod 4$
     • $29 \equiv 1 \pmod 4$

     No sign flip: $$\left(\frac{7}{29}\right) = \left(\frac{29}{7}\right).$$ Reduce $29$ mod $7$: $29 \equiv 1 \pmod 7$, so $$\left(\frac{29}{7}\right) = \left(\frac{1}{7}\right) = 1.$$

   • Step 6: Combine $$\left(\frac{14}{29}\right) = \left(\frac{2}{29}\right)\left(\frac{7}{29}\right) = (-1)\cdot 1 = -1.$$

   So $$\left(\frac{29}{43}\right) = -1.$$

   • Conclusion

     $x^2 \equiv 29 \pmod{43}$ has no solution.

6. Explain why the “sign flip” only occurs when both primes are $\equiv 3 \pmod 4$.

   Solution

   Explain why the “sign flip” only occurs when both primes are $\equiv 3 \pmod 4$.

   • The law says: $$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{(p-1)(q-1)}{4}}.$$
   • The exponent $\frac{(p-1)(q-1)}{4}$ is an integer.
   • Look at $(p-1)/2$ and $(q-1)/2$:
     • If $p \equiv 1 \pmod 4$, then $(p-1)/2$ is even.
     • If $p \equiv 3 \pmod 4$, then $(p-1)/2$ is odd.
   • The exponent is $$\frac{(p-1)(q-1)}{4} = \frac{p-1}{2}\cdot\frac{q-1}{2}.$$
   • This product is odd only when both factors are odd, i.e., when both $p$ and $q$ are $\equiv 3 \pmod 4$.
   • When the exponent is odd, $(-1)^{\text{odd}} = -1$ → sign flip.
     Otherwise, it is $+1$ → no sign flip.
7. Give an example of primes $p$ and $q$ where $\left(\frac{p}{q}\right)=1$ but $\left(\frac{q}{p}\right)=-1$.

   Solution

   Give an example of primes $p$ and $q$ where $\left(\frac{p}{q}\right)=1$ but $\left(\frac{q}{p}\right)=-1$.

   We need both primes $\equiv 3 \pmod 4$ and a pair where the symbols differ.

   • Take $p=3$, $q=11$ (from the chapter’s example).

     • We computed:
       • $\left(\frac{3}{11}\right) = 1$
       • $\left(\frac{11}{3}\right) = -1$

   So $p=3$, $q=11$ is a valid example.

8. Show that if $p \equiv 1 \pmod 4$, then $\left(\frac{-1}{p}\right)=1$ using only the definition of quadratic residues.

   Solution

   Show that if $p \equiv 1 \pmod 4$, then $\left(\frac{-1}{p}\right)=1$ using only the definition of quadratic residues.

   We must show that $-1$ is a square mod $p$.

   • Since $p \equiv 1 \pmod 4$, we can write $p = 4k+1$ for some integer $k$.
   • Consider the number $a = 2k$. Then $$a^2 = (2k)^2 = 4k^2.$$
   • Compute $a^2$ modulo $p$:
     • Note that $p = 4k+1 \Rightarrow 4k \equiv -1 \pmod p$.
     • Multiply both sides by $k$: $$4k^2 \equiv -k \pmod p.$$
     This alone doesn’t yet give $-1$, so let’s use a more standard trick:
   • A classic argument:
     • Since $p \equiv 1 \pmod 4$, $(p-1)/2$ is even. Let $(p-1)/2 = 2m$.
     • Consider $g^{(p-1)/2}$ for a primitive root $g$ modulo $p$: $$g^{(p-1)/2} \equiv -1 \pmod p.$$
     • But $(p-1)/2 = 2m$, so $$g^{(p-1)/2} = g^{2m} = (g^m)^2.$$
     • Thus $-1 \equiv (g^m)^2 \pmod p$, so $-1$ is a square modulo $p$.

   Therefore, by the definition of quadratic residue, $\left(\frac{-1}{p}\right)=1$.

   (If you haven’t introduced primitive roots, you could instead use a counting or pairing argument on the set of residues, but the conclusion is the same: $-1$ is a square when $p \equiv 1 \pmod 4$.)

9. For primes $p \equiv 1 \pmod 8$, explain why $2$ must be a quadratic residue modulo $p$.

   Solution

   For primes $p \equiv 1 \pmod 8$, explain why $2$ must be a quadratic residue modulo $p$.

   We want to show $\left(\frac{2}{p}\right)=1$ when $p \equiv 1 \pmod 8$.

   • The second supplementary law says: $$\left(\frac{2}{p}\right) = \begin{cases} 1 & \text{if } p \equiv \pm 1 \pmod 8,\\ -1 & \text{if } p \equiv \pm 3 \pmod 8. \end{cases}$$
   • If $p \equiv 1 \pmod 8$, then $p$ is in the “$\pm 1$” case, so directly: $$\left(\frac{2}{p}\right) = 1.$$
   • Interpreting this:
     • By definition, $\left(\frac{2}{p}\right)=1$ means that there exists some integer $x$ such that $$x^2 \equiv 2 \pmod p.$$
     • So $2$ is a quadratic residue modulo $p$.

   If you prefer a more conceptual explanation, you can say:

   • The pattern of $\left(\frac{2}{p}\right)$ depends only on $p \pmod 8$.
   • When $p \equiv 1 \pmod 8$, the pattern tells us that $2$ behaves like a square modulo $p$.